package datastructure.tree.twochatree;

import java.util.LinkedList;

/**
 * 二叉树深度优先遍历(前中后序遍历)-非递归版本
 *
 * @author 杨 强
 * @package datastructure.tree.two
 * @createTime 2023-03-20 21:55
 */
public class TreeDeepErgodic02 {
    public static void main(String[] args) {
        // 构建一个二叉树
        /*
                1
               / \
              2   3
             /   / \
            4   5   6
         */
        TreeNode node = new TreeNode(
                new TreeNode(new TreeNode(null, 4, null) ,2, null),
                1,
                new TreeNode(new TreeNode(null, 5, null), 3, new TreeNode(null, 6, null))
        );

        // 借助栈
        LinkedList<TreeNode> stack = new LinkedList<>();
        // 当前节点
        TreeNode curr  = node;
        // 最近一次弹栈的元素
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()){
            // 当前节点不为空
            if (curr != null){
                stack.push(curr);
                // 处理左子树
                System.out.println("(前序) " + curr.value);
                curr = curr.left;
            }else {
                // 查看当前栈顶元素, 这个时候肯定左子树已经处理完毕了
                TreeNode peek = stack.peek();

                // 没有右子树的情况
                if (peek.right == null){
                    System.out.println("(中序) " + peek.value);
                    // 弹出栈顶元素
                    pop = stack.pop();
                    System.out.println("(后序) " + pop.value);
                }
                // 右子树处理完成了.
                else if (peek.right == pop){
                    pop = stack.pop();
                    System.out.println("(后序) " + pop.value);
                }
                // 处理右子树
                else {

                    System.out.println("(中序) " + peek.value);
                    // 然后回的时候看右边节点
                    curr = peek.right;
                }
            }
        }
    }


}
